package com.yoshino.leetcode.improve40.first;

class Solution {
    public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }
//        return a / b;
        boolean isP = (a < 0 && b > 0) || (a > 0 && b < 0);
        if (a > 0) {
            a = -a;
        }
        if (b > 0) {
            b = -b;
        }
        int res = 0;
        while (a <= b) {
            int d = b, c = 1;
            while (d >= Integer.MIN_VALUE >> 1 && d + d >= a) {
                d += d;
                c += c;
            }
            a -= d;
            res += c;
        }
        return isP ? -res : res;
    }

    public String addBinary(String a, String b) {
        int n = Math.max(a.length(), b.length()), m = Math.min(a.length(), b.length()), carry = 0, i = m - 1, j = n - 1;
        String maxStr = a.length() > b.length() ? a : b, minStr = a.length() > b.length() ? b : a;
        StringBuilder sb = new StringBuilder();
        while (i >= 0) {
            if (maxStr.charAt(j) != minStr.charAt(i)) {
                // 0 1
                if (carry == 1) {
                    carry = 1;
                    sb.append(0);
                } else {
                    sb.append(1);
                }
            } else {
                if (minStr.charAt(i) == '0') {
                    // 0 0
                    sb.append(carry);
                    carry = 0;
                } else {
                    // 1 1
                    sb.append(carry);
                    carry = 1;
                }
            }
            i--;
            j--;
        }
        while (j >= 0) {
            if (maxStr.charAt(j) == '0') {
                sb.append(carry);
                carry = 0;
            } else {
                // 1
                if (carry == 1) {
                    sb.append(0);
                    carry = 1;
                } else {
                    sb.append(1);
                    carry = 0;
                }
            }
            j--;
        }
        if (carry == 1) {
            sb.append(1);
        }
        return sb.reverse().toString();
    }

    public int[] countBits(int n) {
        int res[] = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            // 10110 -> 1011 的含 1 一样，即res[i] == res[i / 2] i 可以整除 2 时
            res[i] = res[i / 2] + (i % 2);
        }
        return res;
    }
}
